package leetCode;

/**
 * 面试题 17.16. 按摩师
 * https://leetcode.cn/problems/the-masseuse-lcci/description/
 */
class Solution3 {
    public int massage(int[] nums) {
        //1、建立dp表（这里细化成两个表，选和不选）
        int len = nums.length;
        if(len == 0) return 0;
        int[] f = new int[len];//选
        int[] g = new int[len];//不选
        //2、初始化表
        f[0] = nums[0];
        g[0] = 0;
        //3、填表
        for(int i = 1; i < len; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        //4、返回值
        return Math.max(f[len - 1], g[len - 1]);
    }
}